მონაცემთა სტრუქტურა სტეკი
(Stack). ამოცანები რომლებიც
იხსნება სტეკის საშუალებით.
მარიამ გობრონიძე

რა არის სტეკი
Stack არის წრფივი მონაცემთა სტრუქტურა, რომელიც იყენებს
LIFO (Last In, First Out – ბოლოს შეტანილი პირველი გამოდის)
პრინციპს. ეს ნიშნავს, რომ როგორც ელემენტების დამატება
(Push), ისე ამოღება (Pop) ხდება მხოლოდ ერთი ბოლოდან

სტეკის ტიპები
სტატიკური (Fixed Size) Stack – აქვს ფიქსირებული ზომა და ვერ იზრდება ან
მცირდება დინამიურად.
● თუ Stack სავსეა და ვცდილობთ ახალი ელემენტის დამატებას,
წარმოიქმნება Overflow (გადავსების) შეცდომა.
● თუ Stack ცარიელია და ვცდილობთ ელემენტის ამოღებას,
წარმოიქმნება Underflow (დაცარიელების) შეცდომა.

სტეკის ტიპები
დინამიკური (Dynamic Size) Stack – მისი ზომა დინამიურად იცვლება.
● როდესაც Stack ივსება, ის ავტომატურად იზრდება.
● როდესაც Stack ცარიელდება, მისი ზომა მცირდება.
● ძირითადად, ერთ-ერთი საუკეთესო მეთოდი მისი
რეალიზაციისთვის არის ბმული სია (Linked List).

სტეკის ძირითადი ოპერაციები
Stack-ის მართვისთვის საჭიროა შემდეგი ოპერაციები:
•
•
•
•
•

push() – ელემენტის დამატება Stack-ში.
pop() – ელემენტის ამოღება Stack-დან.
top() ან peek() – აბრუნებს ზედა ელემენტს მისი წაშლის გარეშე.
isEmpty() – აბრუნებს true, თუ Stack ცარიელია, წინააღმდეგ
შემთხვევაში false.
isFull() – აბრუნებს true, თუ Stack სავსეა, წინააღმდეგ შემთხვევაში
false.

Push ოპერაცია (დამატება)
1. ვამოწმებთ, არის თუ არა Stack სავსე.
2. თუ სავსეა (top == capacity - 1), ვაბრუნებთ Overflow
შეცდომას.
3. სხვა შემთხვევაში, ვზრდით top ინდექსს (top = top + 1) და
ვამატებთ ახალ ელემენტს

Pop ოპერაცია (ამოღება)
1. ვამოწმებთ, არის თუ არა Stack ცარიელი.
2. თუ ცარიელია (top == -1), ვაბრუნებთ Underflow შეცდომას.
3. სხვა შემთხვევაში, ვინახავთ ზედა ელემენტის
მნიშვნელობას, ვამცირებთ top ინდექსს (top = top - 1) და
ვაბრუნებთ წაშლილ ელემენტს.

Top (Peek) ოპერაცია
1. ვამოწმებთ, არის თუ არა Stack ცარიელი.
2. თუ ცარიელია (top == -1), ვბეჭდავთ: “Stack ცარიელია”.
3. სხვა შემთხვევაში, ვაბრუნებთ ელემენტს, რომელიც
მდებარეობს top ინდექსზე.

isEmpty ოპერაცია
1. ვამოწმებთ top ინდექსს.
2. თუ (top == -1), Stack ცარიელია → აბრუნებს true.
3. სხვა შემთხვევაში, Stack არ არის ცარიელი → აბრუნებს false.

isFull ოპერაცია
1. ვამოწმებთ top ინდექსს.
2. თუ (top == capacity - 1), Stack სავსეა → აბრუნებს true.
3. სხვა შემთხვევაში, Stack არ არის სავსე → აბრუნებს false.

Stack-ის იმპლემენტაცია
Stack-ის რეალიზაცია შესაძლებელია სხვადასხვა მეთოდით:
1. მასივები (Array) – გამოიყენება ფიქსირებული ზომის მასივები.
2. ბმული სია (Linked List) – უფრო მოქნილი მეთოდი, რომელიც Stackის ზომის დინამიური ცვლილების საშუალებას იძლება.
3. Deque (ორ-მხრივი რიგი) – სტრუქტურა, რომელიც საშუალებას
გვაძლევს ელემენტები დავამატოთ ან წავშალოთ ორივე
ბოლოდან.

Valid Parentheses
ვთქვათ, მოცემულია სტრიქონი s, რომელიც შეიცავს სხვადასხვა ტიპის
ფრჩხილებს: {}, (), და []. საინტერესოა დავადგინოთ, არის თუ არა ეს
ფრჩხილები დაბალანსებული. დაბალანსებულია ნიშნავს, რომ
თითოეულ “გახსნის” ფრჩხილს შესაბამისი “დახურვის” ფრჩხილი უნდა
ჰქონდეს სწორი თანმიმდევრობით.

მაგალითად
“[{()}]” — ყველა ფრჩხილი სწორად არის ჩასმული და დახურული
“[()()]{}” — ყველა ფრჩხილი სწორად არის ჩასმული და დახურული
“([]” — აკლია დამხურავი )
“([{]})” — ფრჩხილები არასწორადაა ჩასმული

ამოვხსნათ სტეკის გამოყენებით
თითოეული გამხსნელი ფრჩხილი სტეკში თავსდება.
როცა ვხვდებით დამხურავ ფრჩხილს, ვამოწმებთ, ემთხვევა
თუ არა სტეკის ზედა ელემენტს.
თუ ემთხვევა – ვშლით ზედა ელემენტს.
ბოლოს, თუ სტეკი ცარიელია – გამონათქვამში ფრჩხილები
სწორადაა გამოყენებული.

1. გამოვაცხადოთ სტეკი.
2. განვიხილოთ სტრიქონის თითოეული სიმბოლო:
○ თუ სიმბოლო არის გამხსნელი ფრჩხილი ((, {, [),
ჩავამატოთ სტეკში.
○ თუ სიმბოლო არის დამხურავი ფრჩხილი:
■ შევამოწმოთ, სტეკი ცარიელი ხომ არ არის და სტეკის
ბოლო ელემენტი შეესაბამება თუ არა დამხურავ
ფრჩხილს.
■ თუ კი – ამოვაგდოთ ელემენტი სტეკიდან.
■ თუ არა – გამონათქვამში / წინადადებაში არასწორადაა
გამოყენებული ფრჩხილები
3. დაბრუნდეს true, თუ სტეკი ცარიელია, false – წინააღმდეგ
შემთხვევაში.

Implement Stack using Queues

ამოცანა
გავაკეთოთ სტეკის (Last-In-First-Out - LIFO) იმიტაცია მხოლოდ ორი რიგის
გამოყენებით, ისე რომ დავიცვათ სტეკის ტიპური ოპერაციები :
●

push(x) – ამატებს ელემენტს სტეკის ზედა ნაწილში

●

pop() – შლის და აბრუნებს ზედა ელემენტს

●

top() – აბრუნებს ზედა ელემენტს წაშლის გარეშე

●

empty() – ამოწმებს ცარიელია თუ არა სტეკი

შეზღუდვები
მხოლოდ რიგის (queue) სტანდარტული ოპერაციების გამოყენებაა
ნებადართული:
●

ელემენტის დამატება ბოლოში (enqueue/push to back)

●

ელემენტის წაშლა თავიდან (dequeue/pop from front)

●

ზომის შემოწმება

●

შემოწმება არის თუ არა ცარიელი?!

იდეა
📌 Stack არის LIFO
აQueue რის FIFO
Stack-ის იმიტაცია queue-ების მეშვეობით საჭიროებს ელემენტების რიგის
ინვერსიას
გამოსავალი: ყოველი push ოპერაციისას ახალი ელემენტი ხვდება რიგის
თავში
q1 – ძირითადი რიგი (stack-ის როლი)
q2 – დამხმარე რიგი

ელემენტის დამატება
push(x):
1. დაამატე x დამხმარე რიგში q2
2. გადააადგილე ყველა ელემენტი q1-დან q2-ში
3. გაცვალე q1 და q2
➡️შედეგი: q1-ის თავშია ბოლოს დამატებული ელემენტი
➡️Stack-ის top ოპერაცია ხდება queue-ის front

ალგორითმები (pop, top, empty)
pop():
➡️წაშალე ელემენტი q1-ის თავიდან
top():
➡️დააბრუნე q1[0] ელემენტი წაშლის გარეშე
empty():
➡️შეამოწმე len(q1) == 0

ახალ ელემენტს ვამატებთ q2-ში.
შემდეგ ყველა ელემენტი q1-დან გადაგვაქვს q2-ში.
ბოლოს q1 ხდება q2, ხოლო q2 ხელახლა ცარიელდება.

სირთულის შეფასება

Implement Queue using Stacks
ამოცანის მიზანია ისეთი მონაცემთა სტრუქტურის — MyQueue — იმპლემენტაცია,
რომელიც იმუშავებს როგორც FIFO (First-In-First-Out) რიგი, მხოლოდ სტეკის
სტანდარტული ოპერაციების გამოყენებით:
●

push to top

●

peek/pop from top

●

size

●

is empty

აღწერა
MyQueue კლასს უნდა ჰქონდეს შემდეგი მეთოდები:
●

push(x) — დაამატოს ელემენტი რიგის ბოლოს.

●

pop() — წაშალოს და დააბრუნოს რიგის თავზე მყოფი ელემენტი.

●

peek() — დააბრუნოს რიგის თავზე მყოფი ელემენტი წაშლის გარეშე.

●

empty() — შეამოწმოს, ცარიელია თუ არა რიგი.

იდეა
რიგის FIFO ლოგიკის მისაღებად ვიყენებთ ორ სტეკს: in_stack და out_stack.
●

ყველა ახალი ელემენტი ემატება in_stack-ში.

●

როდესაც საჭიროა წაკითხვა ან წაშლა რიგის თავიდან, in_stack-ის ელემენტები
გადადის out_stack-ში — ასე შეგვიძლია ელემენტების მიმდევრობის შებრუნება
და FIFO ლოგიკის დაცვა.

ეს გადატანა ხდება მხოლოდ მაშინ, როდესაც out_stack ცარიელია, რაც
უზრუნველყოფს ოპერაციების ეფექტურობას (ამორტიზირებული O(1)).

სირთულის შეფასება
დროითი სირთულე:
●

push() — O(1)

●

pop() — O(1)

●

peek() — O(1)

●

empty() — O(1)

მეხსიერება: O(n), სადაც n — რიგში მყოფი ელემენტების რაოდენობა.

მინიმალური ელემენტის მქონე სტეკი
🔹 ამოცანა: შექმენით სტეკის სტრუქტურა, რომელიც გარდა სტანდარტული
ოპერაციებისა (push, pop, top), უზრუნველყოფს მინიმალური ელემენტის
მიღებას O(1) დროში.
🔹 სტანდარტული სტეკი არ ინახავს მინიმუმს, ამიტომ საჭიროა დამატებითი
ლოგიკა.

ოპერაციები:
●
●
●
●
●

MinStack() — კონსტრუქტორი
push(val) — ელემენტის დამატება
pop() — ელემენტის წაშლა
top() — ზედა ელემენტის ნახვა
getMin() — მინიმალური ელემენტის მიღება

ყველა ოპერაცია უნდა შესრულდეს O(1) დროში

📌 გამოსავალი: ორი სტეკის გამოყენება
● stk1: ინახავს ყველა ელემენტს (ძირითადი სტეკი)
● stk2: ინახავს მინიმუმებს ყოველ ეტაპზე
ყოველ push-ზე, stk2 იღებს მიმდინარე მინიმუმს:
min(val, stk2[-1])
ეს უზრუნველყოფს getMin() ოპერაციის O(1)-ში შესრულებას

სირთულე
დროითი სირთულე (Time Complexity):
●

push, pop, top, getMin — ყველა O(1)

სივრცითი სირთულე (Space Complexity):
●

stk1 და stk2 იზრდება O(n) — n არის ელემენტების რაოდენობა

გმადლობთ ყურადღებისთვის!

